#pragma once

#include <iostream>
#include <assert.h>
#include <map>
#include <vector>
#include <list>
using namespace std;

template<class T>
struct HashNode
{
    typedef HashNode<T> self;

    HashNode(const T& data)
    :_next(nullptr),_data(data)
    {}

    self* _next = nullptr;
    T _data;
};

template<class K,class T,class Cmp>
class hashtable;

template<class K,class T,class Cmp>
struct __HTIterator
{

    typedef HashNode<T> Node;
    typedef hashtable<K,T,Cmp> HT;
    typedef __HTIterator<K,T,Cmp> Self;
    Node* _node;
    HT* _ht;
    Cmp cmp;

    __HTIterator(Node* node,HT* ht)
    :_node(node),_ht(ht)
    {}

    Self& operator++()
    {
        if(_node->_next)
        {
            _node = _node->_next;
        }
        else
        {
            size_t hashi = cmp(_node->_data) % _ht->_tables.size();
            hashi++;
            while(hashi != _ht->_tables.size())
            {
                if(_ht->_tables[hashi])
                {
                    _node = _ht->_tables[hashi];
                    break;
                }
                hashi++;
            }

            if(hashi == _ht->_tables.size())
            {
                _node = nullptr;
            }
        }
        return *this;
    }

    bool operator!=(const Self& s)
    {
        return _node != s._node;
    }

    T& operator*()
    {
        return _node->_data;
    }

};

template<class K,class T,class Cmp>
class hashtable
{
    //template<class K,class T,class Cmp>
    friend struct __HTIterator<K,T,Cmp>;
    
    typedef HashNode<T> Node;
public:
    typedef __HTIterator<K,T,Cmp> iterator;

    iterator begin()
    {
        for(int i = 0; i < _tables.size(); i++)
        {
            if(_tables[i])
            {
                return iterator(_tables[i],this);
            }
        }
        return end();
    }

    iterator end()
    {
        return iterator(nullptr,this);
    }

    hashtable(size_t size = 10);

    hashtable(const hashtable<K,T,Cmp>& h);

    hashtable<K,T,Cmp>& operator=(hashtable<K,T,Cmp> h);

    bool insert(const T& data);

    iterator find(const T& data);

    void print();

    bool erase(const T& data);

    ~hashtable();
private:
    vector<Node*> _tables;
    size_t _n = 0;
    Cmp cmp;
};

template<class K,class T,class Cmp>
hashtable<K,T,Cmp>::hashtable(size_t size)
{
    _tables.resize(size,nullptr);
}

template<class K,class T,class Cmp>
hashtable<K,T,Cmp>::hashtable(const hashtable<K,T,Cmp>& h)
{
    _tables.resize(h._tables.size(),nullptr);
    for(int i = 0; i < h._tables.size(); i++)
    {
        Node* cur = h._tables[i];
        while(cur)
        {
            Node* newnode = new Node(cur->_data);
            newnode->_next = _tables[i];
            _tables[i] = newnode;

            cur = cur->_next;
        }
    }

    _n = h._n;
}

template<class K,class T,class Cmp>
hashtable<K,T,Cmp>& hashtable<K,T,Cmp>::operator=(hashtable<K,T,Cmp> h)
{
    _tables.swap(h._tables);
    _n = h._n;
    return *this;
}

template<class K,class T,class Cmp>
bool hashtable<K,T,Cmp>::insert(const T& data)
{
    if(find(data) != end())
    {
        return false;
    }

    if(_n == _tables.size())//扩容
    {
        vector<Node*> newtables(_tables.size() * 2,nullptr);
        for(int i = 0; i < _tables.size(); i++)
        {
            Node* cur = _tables[i];
            while(cur)
            {
                Node* next = cur->_next;
                size_t Fhashi = cmp(cur->_data) % newtables.size();

                cur->_next = newtables[Fhashi];
                newtables[Fhashi] = cur;

                cur = next;
            }
            _tables[i] = nullptr;
        }
        _tables.swap(newtables);
    }

    size_t hashi = cmp(data) % _tables.size();
    Node* newnode = new Node(data);

    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    ++_n;
    return true;
}

template<class K,class T,class Cmp>
__HTIterator<K,T,Cmp> hashtable<K,T,Cmp>::find(const T& data)
{
    size_t hashi = cmp(data) % _tables.size();

    Node* cur = _tables[hashi];
    if(cur)
    {
        if(cur->_data == data)
        {
            return iterator(cur,this);
        }
        cur = cur->_next;
    }
    return iterator(nullptr,this);
}

template<class K,class T,class Cmp>
hashtable<K,T,Cmp>::~hashtable()
{
    for(int i = 0; i < _tables.size(); i++)
    {
        Node* cur = _tables[i];
        while(cur)
        {
            Node* next = cur->_next;
            delete cur;
            cur = next;
        }
    }
    _n = 0;
}

template<class K,class T,class Cmp>
void hashtable<K,T,Cmp>::print()
{
    for(int i = 0; i < _tables.size(); i++)
    {
        Node* cur = _tables[i];
        while(cur)
        {
            Node* next = cur->_next;
            cout << cmp(cur->_data) << "   ";
            cur = next;
        }
        cout << endl;
    }
}

template<class K,class T,class Cmp>
bool hashtable<K,T,Cmp>::erase(const T& data)
{
    size_t hashi = cmp(data) % _tables.size();
    Node* cur = _tables[hashi];
    Node* prev = nullptr;
    while(cur)
    {
        if(cur->_data == data)
        {
            if(prev == nullptr)
            {
                _tables[hashi] = cur->_next;
            }
            else
            {
                prev->_next = cur->_next;
            }
            --_n;
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}
















namespace dew
{

    enum State
    {
        EMPTY,
        EXIST,
        DELETE
    };

    template<class K,class V>
    struct HashData
    {
        pair<K,V> _data;
        State _state = EMPTY;
    };


    template<class K>
    struct HashFunc
    {
        int operator()(const K& key)
        {
            return (int)key;
        }
    };

    struct HashFuncString
    {
        int operator()(const string& s)
        {
            int ch = 0;
            for(auto e: s)
            {
                ch += e;
            }
            return ch;
        }
    };


    template<class K,class V,class Hash = HashFunc<K>>
    class hashtable
    {
    public:
        hashtable(size_t size = 10);


        HashData<K,V>* find(const K& key);
        bool insert(const pair<K,V>& kv);
        bool erase(const K& key);
        void print()
        {
            for(auto& e: _tables)
            {
                if(e._state == EXIST)
                {
                    cout << e._data.first << endl;
                }
            }
        }
    private:
        vector<HashData<K,V>> _tables;
        size_t _n = 0; //实际存储的个数
        Hash ch;
    };

    template<class K,class V,class Hash>
    HashData<K,V>* hashtable<K,V,Hash>::find(const K& key)
    {
        size_t hashi = ch(key) % _tables.size();
        while(_tables[hashi]._state != EMPTY)
        {
            if(_tables[hashi]._state == EXIST && _tables[hashi]._data.first == key)
            {
                return &_tables[hashi];
            }
            hashi++;
            hashi %= _tables.size();
        }

        return nullptr;
    }

    template<class K,class V,class Hash>
    hashtable<K,V,Hash>::hashtable(size_t size)
    {
        _tables.resize(size);
    }

    template<class K,class V,class Hash>
    bool hashtable<K,V,Hash>::insert(const pair<K,V>& kv)
    {
        if(find(kv.first))
        {
            return false;
        }
        if((double)_n / (double)_tables.size() >= 0.7)
        {
            hashtable<K,V,Hash> newht(_tables.size() * 2);
            //遍历旧表，映射到新表
            for(auto& e: _tables)
            {
                if(e._state == EXIST)
                {
                    newht.insert(e._data);
                }
            }
            _tables.swap(newht._tables);
        }

        size_t hashi = ch(kv.first) % _tables.size();
        while(_tables[hashi]._state == EXIST)
        {
            hashi++;
            hashi %= _tables.size();
        }

        _tables[hashi]._data = kv;
        _tables[hashi]._state = EXIST;
        ++_n;
        return true;
    }

    template<class K,class V,class Hash>
    bool hashtable<K,V,Hash>::erase(const K& key)
    {
        HashData<K,V>* ret = find(key);
        if(ret)
        {
            _n--;
            ret->_state = DELETE;
            return true;
        }
        else
            return false;
        
        // size_t hashi = key % _tables.size();
        // while(_tables[hashi]._state != EMPTY)
        // {
        //     if(_tables[hashi]._state == EXIST && _tables[hashi]._data.first == key)
        //     {
        //         _tables[hashi]._state = DELETE;
        //         return true;
        //     }
        //     hashi++;
        //     hashi %= _tables.size();
        // }

        // return false;
    }

}

